package com.lry.basic.algorithm.common;

import java.util.HashMap;
import java.util.Map;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/8/23
 */
public class NumberSum {
    public static void main(String[] args) {
        System.out.println(twoSum1(new int[]{1, 3, 5, 7}, 4));
    }

    /**
     * 查找数组中是否有两个数相加=target
     * @param nums
     * @param target
     * @return
     */
    public static boolean twoSum(int[]nums,int target){
        if(null==nums||nums.length<=1)return false;
        for(int i=0;i<nums.length;++i){
            for(int j=i+1;j<nums.length;++j){
                if(nums[i]+nums[j]==target){
                    return true;
                }
            }
        }
        return false;
    }

    public static int[] twoSum1(int[]nums,int target){
        if(null==nums||nums.length<=1) return new int[]{};
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;++i){
            if(map.containsKey(nums[i])){
                return new int[]{map.get(nums[i]),i};
            }
            map.put(target-nums[i],i);
        }
        return new int[]{};
    }

    //二分搜索
    public static boolean binSearch(int[]nums,int target){
        if(null==nums||nums.length<=0)return false;
        int low = 0;
        int high = nums.length-1;
        while(low<=high){
            int mid = (low+high)>>>1;
            if(target>nums[mid]){
                low = mid+1;
            }else if(target<nums[mid]){
                high = mid-1;
            }else{
                return true;
            }
        }
        return false;
    }
}
